package Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class HasPathSum {
    public static void main(String[] args) {

    }

    public boolean hasPathSum(TreeNode root, int targetSum){
        if(root == null) return false;
        Stack<TreeNode> stackNode = new Stack<>();
        Stack<Integer> stackSum = new Stack<>();
        stackNode.push(root);
        stackSum.push(root.val);
        while(!stackNode.isEmpty()){
            int size = stackNode.size();
            for(int i = 0; i < size; i++){
                TreeNode node = stackNode.pop();
                int sum = stackSum.pop();
                //到叶子结点，判断sum是否等于给定targetSum
                if(node.left == null && node.right == null && sum == targetSum){
                    return true;
                }
                //否则压孩子入栈
                if(node.right != null){
                    stackNode.push(node.right);
                    stackSum.push(sum + node.right.val);
                }
                if(node.left != null){
                    stackNode.push(node.left);
                    stackSum.push(sum + node.left.val);
                }
            }
        }
        return false;
    }
}
